#include "DRC.h"

//If overlapping return true
bool isOverlap(const Rectangle& rect1, const Rectangle& rect2){
	return (rect1.x1 < rect2.x2 && rect1.x2 > rect2.x1 && rect1.y1 < rect2.y2 && rect1.y2 > rect2.y1);
}

//Line scan traversal to determine whether there is overlap
void scan_line(vector<Rectangle>& Rectangles,set<int>& error_index){
	vector<pair<int,int>> temp;
	for(int i = 0;i < Rectangles.size();i++){
		temp.push_back(make_pair(Rectangles[i].x1,i));
		temp.push_back(make_pair(Rectangles[i].x2,i));
	}
	sort(temp.begin(),temp.end());

	vector<int> active_index;

	for(int i = 0; i< temp.size();i++){
		Rectangle current_r = Rectangles[temp[i].second];
		if(temp[i].first == current_r.x1){
			active_index.push_back(temp[i].second);
		}else{
			auto iter = find(active_index.begin(),active_index.end(),temp[i].second);
			if(iter != active_index.end()){
				active_index.erase(iter);
			}
		}

		for(auto j:active_index){
			if(j != temp[i].second){
				Rectangle other_r = Rectangles[j];
				if(isOverlap(current_r,other_r)){
					error_index.insert(temp[i].second);
					error_index.insert(j);
				}
			}
		}
	}
}

